
// leetcode 
//class LRUCache {
//
//    class ListNode {
//        ListNode prev;
//        ListNode next;
//        int val;
//        int key;
//
//        public ListNode(int key, int val) {
//            this.val = val;
//            this.key = key;
//        }
//
//        public ListNode() {
//
//        }
//    }
//
//    // 头节点和尾巴节点
//    ListNode head;
//    ListNode last;
//
//    // key, node 记录 key 与 ListNode 的对应关系
//    HashMap<Integer, ListNode> hash;
//    int capacity;
//    int curSize;
//
//    public LRUCache(int capacity) {
//        hash = new HashMap<>();
//        this.capacity = capacity;
//        // 虚拟头节点和虚拟尾巴节点
//        head = new ListNode();
//        last = new ListNode();
//        head.next = last;
//        last.prev = head;
//    }
//
//    public int get(int key) {
//        ListNode cur = hash.get(key);
//        if (cur != null) {
//            // 此时节点存在，需要将该节点移动到头节点，并删除该节点
//            removeNode(cur);
//            addFirst(cur);
//            return cur.val;
//        } else {
//            return -1;
//        }
//    }
//
//    public void removeNode(ListNode node) {
//        node.prev.next = node.next;
//        node.next.prev = node.prev;
//    }
//
//    public void addFirst(ListNode node) {
//        node.prev = head;
//        node.next = head.next;
//        head.next.prev = node;
//        head.next = node;
//    }
//
//    public void put(int key, int value) {
//        ListNode node = hash.get(key);
//        if (node != null) {
//            // 此时节点存在，需要将该节点移动到头节点，并删除该节点
//            node.val = value;
//            removeNode(node);
//            addFirst(node);
//            return;
//        } else {
//            // 头插法，链表尾巴节点代表最久未使用的节点
//            ListNode cur = new ListNode(key, value);
//            hash.put(key, cur);
//            addFirst(cur);
//            curSize++;
//
//            if (curSize > capacity) {
//                // 删除尾巴节点
//                ListNode lastPrev = last.prev;
//                removeNode(lastPrev);
//                hash.remove(lastPrev.key);
//                curSize--;
//            }
//        }
//    }
//
//}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */